package leetcode.code1594;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	int MOD = (int) 1e9 + 7;

	public int maxProductPath(int[][] grid) {
		int m = grid.length;
		int n = grid[0].length;
		long[][] maxs = new long[m][n];// 用int心态崩
		long[][] mins = new long[m][n];
		maxs[0][0] = grid[0][0];
		mins[0][0] = grid[0][0];
		for (int i = 1; i < n; i++) {
			long cur[] = this.mr(grid, i, maxs, mins);
			maxs[0][i] = cur[0];
			mins[0][i] = cur[1];
		}
		for (int i = 1; i < m; i++) {
			long cur[] = this.mc(grid, i, maxs, mins);
			maxs[i][0] = cur[0];
			mins[i][0] = cur[1];
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				long cur[] = this.mm(grid, i, j, maxs, mins);
				maxs[i][j] = cur[0];
				mins[i][j] = cur[1];
			}
		}
		return maxs[m - 1][n - 1] >= 0 ? (int) (maxs[m - 1][n - 1] % MOD) : -1;
	}

	private long[] mr(int[][] grid, int i, long[][] maxs, long[][] mins) {
		int cur = grid[0][i];
		long max = cur * maxs[0][i - 1];
		long min = cur * mins[0][i - 1];
		return new long[] { Math.max(max, min), Math.min(max, min) };
	}

	private long[] mc(int[][] grid, int i, long[][] maxs, long[][] mins) {
		int cur = grid[i][0];
		long max = cur * maxs[i - 1][0];
		long min = cur * mins[i - 1][0];
		return new long[] { Math.max(max, min), Math.min(max, min) };
	}

	private long[] mm(int[][] grid, int i, int j, long[][] maxs, long[][] mins) {
		int cur = grid[i][j];
		long maxUp = maxs[i - 1][j] * cur;
		long minUp = mins[i - 1][j] * cur;
		long maxLeft = maxs[i][j - 1] * cur;
		long minLeft = mins[i][j - 1] * cur;
		long max = Math.max(Math.max(maxUp, minUp), Math.max(maxLeft, minLeft));
		long min = Math.min(Math.min(maxUp, minUp), Math.min(maxLeft, minLeft));
		return new long[] { max, min };
	}

	@Override
	public void debug1() {
		HelpDebug.compare(-1, this.maxProductPath(HelpDebug.str2array1("[[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]")));
	}

	@Override
	public void debug2() {
		HelpDebug.compare(8, this.maxProductPath(HelpDebug.str2array1("[[1,-2,1],[1,-2,1],[3,-4,1]]")));
	}

	@Override
	public void debug3() {
		HelpDebug.compare(2, this.maxProductPath(HelpDebug.str2array1("[[1,4,4,0],[-2,0,0,1],[1,-1,1,1]]")));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		HelpDebug.compare(0, this.maxProductPath(HelpDebug.str2array1("[[1,3],[0,-4]]")));

	}

	public void debug5() {
		// TODO Auto-generated method stub
		HelpDebug.compare(459630706, this.maxProductPath(HelpDebug.str2array1(
				"[[1,-1,2,1,-1,0,0,4,3,2,0,-2,-2],[-2,3,3,-1,-1,0,0,-2,4,-3,3,0,0],[-4,-1,-1,-2,2,-1,-2,-2,0,3,-1,-4,1],[-3,4,-3,0,-3,1,-3,1,4,4,-4,-4,-2],[3,-3,1,0,-1,-4,-4,-4,3,2,2,3,3],[2,-1,-1,-4,-3,-3,4,2,3,4,4,-4,0],[4,-1,2,-3,-1,-1,-3,-4,4,4,4,-3,-1],[-3,-4,4,-2,-1,2,3,-1,2,3,4,4,-4],[-3,-1,-2,1,1,-1,-3,-4,-3,1,-3,3,-4],[2,4,4,4,-3,-3,1,-1,3,4,-1,1,4],[2,-2,0,4,-1,0,-2,4,-4,0,0,2,-3],[1,1,-3,0,-4,-4,-4,-4,0,-1,-4,-1,0],[3,-1,-3,-3,-3,-2,-1,4,-1,-2,4,2,3]]")));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug5();
		so.debug4();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
